package com.licw.java.sort;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.List;

class Heap<E> {
    private final List<E> list = new ArrayList<>();
    private Comparator<E> comparator;

    public Heap() {
        this.comparator = (o1, o2) -> ((Comparable<E>) o1).compareTo(o2);
    }

    public Heap(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    public Heap(Collection<E> collection){
        list.addAll(collection);
        // heapify
        
    }

    public void addAll(Collection<E> arr) {
        for (E num : arr) {
            this.add(num);
        }
    }

    public void addAll(E[] arr) {
        for (E num : arr) {
            this.add(num);
        }
    }

    public void add(E num) {
        list.add(num);
        int curIdx = list.size() - 1, fIdx = (curIdx - 1) / 2;
        while (curIdx > 0
                && this.comparator.compare(list.get(curIdx), list.get(fIdx)) < 0) {
            swap(curIdx, fIdx);
            curIdx = fIdx;
            fIdx = (curIdx - 1) / 2;
        }
    }

    public E remove() {
        if (list.isEmpty()) return null;

        E res = list.get(0);
        swap(0, list.size() - 1);
        list.remove(list.size() - 1);

        int curIdx = 0, sz = list.size();
        while (true) {
            int sawpIdx = curIdx, leftSonIdx = curIdx * 2 + 1, rightSonIdx = curIdx * 2 + 2;
            if (leftSonIdx < sz && this.comparator.compare(list.get(leftSonIdx), list.get(sawpIdx)) < 0) {
                sawpIdx = leftSonIdx;
            }
            if (rightSonIdx < sz && this.comparator.compare(list.get(rightSonIdx), list.get(sawpIdx)) < 0) {
                sawpIdx = rightSonIdx;
            }

            if (curIdx != sawpIdx) {
                swap(curIdx, sawpIdx);
                curIdx = sawpIdx;
            } else break;
        }
        return res;
    }

    private void swap(int i, int j) {
        E tmp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, tmp);
    }

    public boolean isEmpty() {
        return this.size() == 0;
    }

    public int size() {
        return list.size();
    }


    public static void main(String[] args) {
//        PriorityQueue<List<Integer>> heap = new PriorityQueue<>();
        Heap<Long> heap = new Heap<>();
//        heap.addAll(
        Long[] arr = new Long[]{10L, 11L, 6L, 34L, 23L, 2L, 100L};
        for (int i = 0; i <arr.length; i++) {
            heap.add(arr[i]);
        }
        while (!heap.isEmpty()) {
            System.out.println(heap.remove());
        }
    }


}
